Les correspondances mathématiques et la modélisation de données constituent le pont entre la théorie abstraite des ensembles et la réalité computationnelle. Dans ce cadre, un algorithme agit comme une transformation formelle et déterministe où une entrée structurée est traitée par des instructions précises pour produire une sortie correcte. Cela établit la base logique de toute l'architecture logicielle et des bases de données.
Les propriétés d'un algorithme
Un algorithme est une méthode étape par étape pour résoudre un problème, caractérisée par sept piliers essentiels :
- Entrée : L'algorithme reçoit des données à partir d'un ensemble spécifié.
- Sortie : L'algorithme produit un résultat (la solution) à partir d'un ensemble spécifié.
- Précision : Chaque étape est formulée avec une clarté absolue.
- Déterminisme : Les résultats intermédiaires sont uniques et déterminés uniquement par les entrées et les étapes précédentes.
- Finitude : Le processus s'achève après un nombre fini d'instructions.
- Exactitude : La sortie résout le problème comme prévu.
- Généralité : La procédure s'applique à une classe entière d'entrées, et non à un seul cas.
Algorithme 4.1.1 : Trouver le maximum de trois nombres
Cette relation ternaire simple illustre la précision et le déterminisme. Quelles que soient les valeurs de $a, b,$ et $c$, les étapes suivent un chemin logique rigide.
Trace du pseudocode
max3(a, b, c) {
grand = a
si (b > grand) grand = b
si (c > grand) grand = c
retourner grand
}Modélisation de données et invariants de boucle
Dans des structures de données plus complexes, telles que les séquences ($s_1, ..., s_n$), nous utilisons l'algorithme 4.1.2. Pour garantir que ces algorithmes sont corrects, nous nous appuyons sur l'induction et le concept d'un invariant de boucle.
Algorithme 4.1.2 : Trouver le maximum dans une séquence
max(s, n) {
grand = s_1
pour i = 2 à n
si (s_i > grand)
grand = s_i
retourner grand
}Invariant de boucle : "grand est la plus grande valeur dans la sous-séquence $s_1, ..., s_i$". Cette propriété reste vraie à chaque itération, prouvant la correction par induction.
🎯 Principe fondamental : Validité de la correspondance
Une fonction mathématique valide exige que chaque élément du domaine soit associé à exactement un élément dans le codomaine. Une flèche manquante ou plusieurs flèches partant d'une même source invalide le statut de fonction, reflétant pourquoi les algorithmes non déterministes ou incomplets échouent en pratique.